/*
*       版权归 仓库所有者cc01cc(cc01cc@foxmail.com) 所有
*       此文件内的源码在遵循以下条例的前提下，提供自由使用：
*       一. 未经 仓库所有者cc01cc(cc01cc@foxmail.com) 书面许可:
*           1. 任何企业单位组织严禁将源码直接用于商业以及一切涉及获利的行为。
*       二. 未经 仓库所有者cc01cc(cc01cc@foxmail.com) 许可:
*           1. 任何企业单位组织严禁将源码以任何形式用于商业以及一些涉及获利的行为。
*           2. 任何个人严禁将源码以任何形式用于商业以及一些涉及获利的行为。
*       三. 申明:
*           1. 源码作者保留所有专利权，并开放专利使用权。
*           2. 若使用源码造成任何形式的损失，源码作者不承担任何责任。
*           3. 若由于使用源码造成任何形式的损失，由使用者提供全部赔偿。
*       四. 除上述之外，所有未定义事项遵循 AGPL-3.0 许可协议
*/

/*
 *     Copyright (c) 2021. cc01cc(cc01cc@foxmail.com). All rights reserved.
 *
 *     This is part of this file.
 *
 *     This file is free software: you can redistribute it and/or modify
 *     it under the terms of the GNU Affero General Public License as published
 *     by the Free Software Foundation, either version 3 of the License, or
 *     (at your option) any later version.
 *
 *     This file is distributed in the hope that it will be useful,
 *     but WITHOUT ANY WARRANTY; without even the implied warranty of
 *     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *     GNU Affero General Public License for more details.
 *
 *     You should have received a copy of the GNU Affero General Public License
 *     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <stdio.h>
#include <stdlib.h>

//  可通过修改 max_line 调整输入的最大行数，此处为 20
#define max_line 20
#define max_data max_line*(max_line+1)/2
struct Triangle
{
    // 行号
    int row;
    // 列号
    int column;
    // 存储节点的值，用于累加求最大值
    int value;
    // 存储节点原始的值，用于路径输出
    int origin_value;
    //  子节点的索引/下标信息
    int i_path_from;
};
typedef struct Triangle Triangle;

void getData(Triangle *triangle, int n_line);
void findMax(Triangle *triangle, int n_line);
void printRoute(Triangle *triangle,int n_line);
int main()
{
    int n_line = 0;
    Triangle triangle[max_data];

    printf("please enter the number of line: ");
    scanf("%d", &n_line);

    if(n_line > max_line || n_line == 0) return 0;

    getData(triangle, n_line);
    findMax(triangle, n_line);

    printf("The max value is %d.\n", triangle[0].value);

    printRoute(triangle, n_line);
}

//**************************************************************
//  作用：读取并存储数据
//**************************************************************
void getData(Triangle *triangle, int n_line)
{
    int i_triangle = 0;
    int i, j;
    freopen("tower.txt", "r", stdin);

    for(i = 0; i < n_line; i++)
    {
        for(j = 0; j < i + 1; j++)
        {
            // 行号，列号从0开始
            triangle[i_triangle].row = i;
            triangle[i_triangle].column = j;
            scanf("%d", &triangle[i_triangle].origin_value);
            triangle[i_triangle].value = triangle[i_triangle].origin_value;
            i_triangle++;
        }
    }
}

//**************************************************************
//  作用：寻找最大值
//**************************************************************
void findMax(Triangle *triangle, int n_line)
{
    int i_triangle = 0;
    int i, j;

    // 从倒数第二行的最后一个值开始索引（倒数第一行不需要求和）
    // n_line*(n_line-1)/2 求截止数塔倒数第二行所包含的元素个数
    // 由于下标从0开始，其下标为元素个数 -1；
    i_triangle = n_line*(n_line-1)/2 - 1;
    // i 从倒数第二行开始往上取值
    for(i = n_line-1-1, j = 0; i >= 0; i--)
    {
        // 每一行的个数与所在行数相等（不是行号，因为行号 i 从0开始）
        // j 从右往左取值
        for(j = i; j >= 0; j--)
        {
            // 比较两个子节点的值大小
            // 左侧子节点 i_triangle+i+1 = 当前节点 i_triangle+当前行的节点个数；当前行的节点个数=行数i+1
            // 右侧子节点 i_triangle+i+2 = 左侧子节点 + 1
            if(triangle[i_triangle+i+2].value < triangle[i_triangle+i+1].value)
            {
                triangle[i_triangle].value=triangle[i_triangle].value+triangle[i_triangle+i+1].value;
                triangle[i_triangle].i_path_from = i_triangle+i+1;
            }else
            {
                triangle[i_triangle].value=triangle[i_triangle].value+triangle[i_triangle+i+2].value;
                triangle[i_triangle].i_path_from = i_triangle+i+2;
            }
            i_triangle--;
        }
    }
}

//**************************************************************
//  作用：输出路径
//**************************************************************
void printRoute(Triangle *triangle, int n_line)
{
    int i, j;
    int i_triangle = 0;
    printf("The route is %d", triangle[i_triangle].origin_value);
    for(i = 0; i < n_line - 1; i++)
    {
        i_triangle = triangle[i_triangle].i_path_from;
        printf("->%d", triangle[i_triangle].origin_value);
    }
}
